Section: Scientific Foundations

Theory and applications of three-dimensional visibility

Keywords: effective geometry, robustness, 3D visibility

The notion of 3D visibility plays a fundamental role in computer graphics. In this field, the determination of objects visible from a given point, the extraction of shadows or of penumbra boundaries are examples of visibility computations. In global illumination methods, (e.g. radiosity algorithms), it is necessary to determine, in a very repetitive manner, if two points of a scene are mutually visible. The computations can be excessively expensive. For instance, in radiosity, it is not unusual that 50 to 70% of the simulation time is spent answering visibility queries.

Objects that are far apart may have very complicated and unintuitive visual interactions, and because of this, visibility queries are intrinsically global. This partially explains that, until now, researchers have primarily used ad hoc structures, of limited scope, to answer specific queries on-the-fly. Unfortunately, experience has shown that these structures do not scale up. The lack of a well-defined mathematical foundation and the non-exploitation of the intrinsic properties of 3D visibility result in structures that are not usable on models consisting of many hundreds of thousands of primitives, both from the viewpoint of complexity and robustness (geometric degeneracies, aligned surfaces, etc.).

We have chosen a different approach which consists in computing ahead of time (that is, off-line) a 3D global visibility structure for which queries can be answered very efficiently on-the-fly (on line). The 3D visibility complex – essentially a partition of ray space according to visibility – is such a structure, recently introduced in computational geometry and graphics  [35] , [37] . We approach 3D global visibility problems from two directions: we study, on the one hand, the theoretical foundations and, on the other hand, we work on the practical aspects related to the development of efficient and robust visibility algorithms.

From a theoretical point of view, we study, for example, the problem of computing lines tangent to four among $k$ polytopes. We have shown much better bounds on the number of these tangents than were previously known [2] . These results give a measure of the complexity of the vertices (cells of dimension 0) of the visibility complex of faceted objects, in particular, for triangulated scenes.

From a practical point of view, we have, for example, studied the problem of the complexity for these 3D global visibility structures, considered by many to be prohibitive. The size of these structures in the worst case is $O\left(n^4\right)$, where $n$ is the number of objects in the scene. But we have, in fact, shown that when the objects are uniformly distributed, the complexity is linear in the size of the input [6] . This probabilistic result does not prejudice the complexity observed in real scenes where the objects are not uniformly distributed. However, initial empirical studies show that, even for real scenes, the observed complexity is largely inferior to the theoretical worst-case complexity, as our probabilistic result appears to indicate.

We work on translating these positive signs into efficient algorithms. We study new algorithms for the construction of the visibility complex, with a focus on the complexity and robustness.